package leetcode;

import java.util.*;

public class Code7 {
    public static void main(String[] args) {
        Code7 code7 = new Code7();
        TreeNode treeNode = code7.deserialize("{1,2,#,3,#,4}");
        System.out.println(code7.serialize(treeNode));
    }

    /**
     * This method will be invoked first, you should design your own algorithm
     * to serialize a binary tree which denote by a root node to a string which
     * can be easily deserialized by your own "deserialize" method later.
     */
    public class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }

    /**
     * 中续遍历
     *
     * @param root
     * @return
     */
    public String serialize(TreeNode root) {
        // write your code here
        Deque<TreeNode> treeNodeDeque = new LinkedList<TreeNode>();
        treeNodeDeque.addLast(root);
        TreeNode item;
        String s = "";
        while (treeNodeDeque.size() != 0) {
            item = treeNodeDeque.removeFirst();
            if (item == null) {
                s += "," + "#";
            } else {
                s += "," + item.val;
                treeNodeDeque.addLast(item.left);
                treeNodeDeque.addLast(item.right);
            }
        }
        s=s.substring(1, s.length());
        String[] i =s.split(",");
        for (int a=i.length-1;a>=0;a--){
            if (!i[a].equals("#")){
                s=createString(0,a+1,i);
                break;
            }
        }
        return "{" + s + "}";
    }

    private String createString(int i, int i1, String[] i2) {
        String s="";
        for (int a=0;a<i1;a++) {
            if (a == 0) {
                s += i2[a];
            } else {
                s += "," + i2[a];
            }
        }
        return s;
    }

    /**
     * This method will be invoked second, the argument data is what exactly
     * you serialized at method "serialize", that means the data is not given by
     * system, it's given by your own serialize method. So the format of data is
     * designed by yourself, and deserialize it here as you serialize it in
     * "serialize" method.
     */
    public TreeNode deserialize(String data) {
        // write your code here
        String d = data.substring(1, data.length() - 1);
        data = d;
        String[] list = data.split(",");
        TreeNode[] tlist = new TreeNode[list.length];
        if (list[0].equals("#")) {
            return null;
        }
        tlist[0] = new TreeNode(Integer.parseInt(list[0]));
        for (int a = 1; a < list.length; a++) {
            int father = (a + 1) / 2 - 1;
            TreeNode item = null;
            if (!list[a].equals("#")) {
                item = new TreeNode(Integer.parseInt(list[a]));
            }
            if ((a + 1) % 2 == 0) {
                tlist[father].left = item;
            } else {
                tlist[father].right = item;
            }
            tlist[a] = item;
        }
        return tlist[0];
    }
}
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

/**
 * 前序遍历
 */

class Solution {
    public class TreeNode {
        public int val;
        public TreeNode left, right;

        public TreeNode(int val) {
            this.val = val;
            this.left = this.right = null;
        }
    }
    private static final String spliter = ",";
    private static final String NN = "X";

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        buildString(root, sb);
        return sb.toString();
    }

    private void buildString(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NN).append(spliter);
        } else {
            sb.append(node.val).append(spliter);
            buildString(node.left, sb);
            buildString(node.right,sb);
        }
    }
    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        Deque<String> nodes = new LinkedList<>();
        nodes.addAll(Arrays.asList(data.split(spliter)));
        return buildTree(nodes);
    }

    private TreeNode buildTree(Deque<String> nodes) {
        String val = nodes.remove();
        if (val.equals(NN)) return null;
        else {
            TreeNode node = new TreeNode(Integer.valueOf(val));
            node.left = buildTree(nodes);
            node.right = buildTree(nodes);
            return node;
        }
    }
}